1. Field of the Invention
This invention relates to authentication systems, and more specifically to cryptographic protocols involving public-key signatures.
2. Description of Prior Art
The two earliest kinds of public key authentication systems known in the art can be viewed as extremes. A "zero-knowledge" authentication protocol, although convincing to the recipient, does not allow the recipient to convince anyone else. A "serf-authenticating" digital signature technique, on the other extreme, not only allows the recipient to convince anyone, simply by providing a copy of a signature, but also allows anyone so convinced to convince others without limitation.
"Undeniable signatures" strike a balance, somewhere in between these extremes, protecting both the interests of the signer in ensuring that the signatures are not subsequently misused by the recipient as well as the interests of the recipient in providing possibilities for later verification of signatures by others. The recipient of an undeniable signature is convinced that anyone holding it can challenge its signer and that the signer cannot answer falsely. The reason this works is that the signer is always able to convince anyone that a valid signature is valid and that an invalid signature is invalid. Thus the recipient is at least sure that the signer cannot falsely deny a valid signature.
For the recipient, undeniable signatures do have the advantage over zero-knowledge that the recipient has something that can later, under certain conditions, be used to convince others. But for many practical applications these conditions make the protection offered to the receiver too weak. They require the signer to be available and to cooperate in any subsequent confirmation of a signature. If the signer should refuse to cooperate or become unavailable, as might for instance happen in case of default on the agreement represented by the signature, then the recipient cannot make use of the signature.
The three aforementioned prior art authentication techniques--zero-knowledge, self-authenticating signatures, and undeniable signatures--have been disclosed, respectively, as follows: Goldwasser, Micali, and Rackoff, in "The knowledge complexity of interactive proof-systems," Proceedings of STOC '85, ACM press 1985; Diffie and Hellman, "New directions in cryptography," IEEE Trans. Inform. Theory, IT-22(6), November 1976; and U.S. Pat. No. 4,947,430, titled "Undeniable signature systems," by the present applicant.
Related art discloses how a signer can form a private key that can be used to convert all the undeniable signatures made by that signer into self-authenticating digital signatures, as described by Boyar, Chaum, Damgaard, and Pedersen, in "Convertible undeniable signatures," Proceedings of Crypto '90, Springer-Verlag, 1991. Receivers of the undeniable signatures are convinced that all the signatures can be converted by release of the same secret value. This secret value could be provided by the signer to another party who could not use it to create signatures but could release it later, such as in the case of death of the signer. Not only does this technique require signers to establish secret keys that have to be provided to third parties, but no provision for allowing these third parties to authenticate their acceptance of these keys was disclosed. And of course the conversion to self-authenticating form is all-or-nothing: it either applies to all signatures at once or to no signature at all.
Also disclosed by Boyar et al were means to selectively convert some undeniable signatures to self-authenticating signatures. But no provision for receivers to be convinced of the extent to which this is possible has been disclosed. Verifiability by the receiver of the potential for conversion is of course essential, and again no way to achieve it has been disclosed. In fact, the signer simply providing the corresponding self-authenticating signatures to the third party is functionally equivalent to these techniques.